home *** CD-ROM | disk | FTP | other *** search
Text File | 1997-06-28 | 5.0 KB | 267 lines | [TEXT/CWIE] |
- // Heap.cp
-
- #ifndef Heap_h
- #include "Heap.h"
- #endif
- #ifndef HeapLink_h
- #include "HeapLink.h"
- #endif
- #ifndef Swap_h
- #include "Swap.h"
- #endif
-
- template< class Element >
- Heap< Element >::Heap( Comparator compare )
- : nodeCount( 0 ),
- top( 0 ),
- below( compare )
- {
- Assert( compare != 0 );
- }
-
- template< class Element >
- Heap< Element >::~Heap()
- {
- Assert( nodeCount == 0 );
- Assert( top == 0 );
- }
-
- template< class Element >
- HeapLink<Element>& Heap< Element >::Pop()
- {
- HeapLink<Element>& result = Top();
- Remove( result );
- return result;
- }
-
- template< class Element >
- void Heap< Element >::Add( LinkType& toAdd )
- {
- Assert( toAdd.heap == 0 );
- toAdd.heap = this;
-
- Assert( toAdd.children[0] == 0 );
- Assert( toAdd.children[1] == 0 );
-
- toAdd.path = ++nodeCount;
-
- LinkType **subHeap = ⊤
- LinkType *carrying = &toAdd;
- SinkNode( subHeap, carrying );
-
- Assert( *subHeap == 0 );
- Assert( carrying->path == nodeCount );
- Assert( carrying->children[0] == 0 );
- Assert( carrying->children[1] == 0 );
-
- *subHeap = carrying;
- }
-
- template< class Element >
- void Heap< Element >::Remove( LinkType& toRemove )
- {
- Assert( toRemove.heap == this );
- Assert( nodeCount > 0 );
-
- LinkType *spare( &RemoveLast() );
-
- if ( spare != &toRemove )
- {
- LinkType **subHeap = ⊤
- spare->path = toRemove.path;
- SinkNode( subHeap, spare );
-
- Assert( *subHeap == &toRemove );
- Assert( spare->path == toRemove.path );
-
- *subHeap = spare;
- toRemove.SwapWith( *spare );
- Percolate( subHeap );
- }
-
- toRemove.heap = 0;
- Assert( toRemove.children[0] == 0 );
- Assert( toRemove.children[1] == 0 );
- }
-
-
- template< class Element >
- HeapLink<Element>** Heap< Element >::SubHeap( uint32 path )
- {
- Assert( path <= nodeCount );
- Assert( path >= 1 );
-
- LinkType **subHeap = ⊤
- uint32 remainingPath = path;
-
- while ( remainingPath > 1 )
- {
- Assert( *subHeap != 0 );
- subHeap = &(*subHeap)->children[ remainingPath % 2 ];
- remainingPath /= 2;
- }
-
- Assert( *subHeap != 0 );
- Assert( (*subHeap)->path == path );
- return subHeap;
- }
-
- template< class Element >
- HeapLink<Element>& Heap< Element >::RemoveLast()
- {
- Assert( nodeCount > 0 );
- LinkType **subHeap = SubHeap( nodeCount );
- LinkType& removed = **subHeap;
- *subHeap = 0;
-
- Assert( removed.children[0] == 0 );
- Assert( removed.children[1] == 0 );
- Assert( removed.heap == this );
- Assert( removed.path == nodeCount );
- removed.path = 0;
- nodeCount--;
-
- return removed;
- }
-
- template< class Element >
- void Heap< Element >::SinkNode( LinkType**& subHeap,
- LinkType*& carrying )
- {
- Assert( subHeap != 0 );
- Assert( carrying != 0 );
-
- uint32 path = carrying->path;
-
- while( path > 1 )
- {
- Assert( *subHeap != 0 );
-
- if ( **subHeap > *carrying )
- {
- (*subHeap)->SwapWith( *carrying );
- Swap( *subHeap, carrying );
- }
-
- Assert( path > 1 );
- subHeap = &(*subHeap)->children[ path % 2 ];
- path /= 2;
- }
-
- Assert( path == 1 );
- }
-
- template< class Element >
- void Heap< Element >::Percolate( LinkType** subHeap )
- {
- LinkType& dropping( **subHeap );
-
- while( true )
- {
- Assert( *subHeap == &dropping );
-
- LinkType *left = dropping.children[0];
- LinkType *right = dropping.children[1];
-
- if ( left == 0 )
- {
- Assert( right == 0 );
- break;
- }
-
- if ( dropping > *left && ( right == 0 || *left <= *right ) )
- {
- dropping.SwapWith( *left );
- Swap( *subHeap, left->children[0] );
-
- Assert( left->children[0] == &dropping );
- Assert( *subHeap == left );
-
- subHeap = &left->children[0];
- continue;
- }
-
- if ( right == 0 )
- break;
-
- if ( dropping > *right )
- {
- dropping.SwapWith( *right );
- Swap( *subHeap, right->children[1] );
-
- Assert( right->children[1] == &dropping );
- Assert( *subHeap == right );
-
- subHeap = &right->children[1];
- continue;
- }
-
- break;
- }
- }
-
- template< class Element >
- void Heap< Element >::Validate( LinkType& node, uint32 level ) const
- {
- Assert( node.path > 0 );
- Assert( node.path <= nodeCount );
- Assert( node.heap == this );
- Assert( !node.Null() );
-
- uint32 topBit = 1L << level;
-
- Assert( (node.path & topBit) != 0 );
- Assert( node.path <= ( 2*topBit - 1) );
-
- if ( level == 31 )
- {
- Assert( node.children[0] == 0 );
- Assert( node.children[1] == 0 );
- return;
- }
-
- uint32 rightChild = node.path | (topBit << 1);
- uint32 leftChild = rightChild & ~topBit;
-
- if ( node.children[0] == 0 )
- {
- Assert( leftChild > nodeCount );
- }
- else
- {
- Assert( leftChild <= nodeCount );
- Assert( node.children[0]->path == leftChild );
- Assert( node <= *node.children[0] );
- Validate( *node.children[0], level+1 );
- }
-
- if ( node.children[1] == 0 )
- {
- Assert( rightChild > nodeCount );
- }
- else
- {
- Assert( rightChild <= nodeCount );
- Assert( node.children[1]->path == rightChild );
- Assert( node <= *node.children[1] );
- Validate( *node.children[1], level+1 );
- }
- }
-
- template< class Element >
- void Heap< Element >::Validate() const
- {
- Assert( below != 0 );
-
- if ( nodeCount == 0 )
- {
- Assert( top == 0 );
- }
- else
- {
- Assert( top != 0 );
- Assert( top->path == 1 );
- Validate( *top, 0 );
- }
- }
-